home *** CD-ROM | disk | FTP | other *** search
/ Revista CD Expert 8 / Revista CD Expert nº 08 CD1.iso / Utilitarios / Programacao / Bloodshed Dev-C++ 2.0 / _SETUP.1 / stl_slist.h < prev    next >
C/C++ Source or Header  |  1998-03-08  |  21KB  |  741 lines
  1. /*
  2.  * Copyright (c) 1997
  3.  * Silicon Graphics Computer Systems, Inc.
  4.  *
  5.  * Permission to use, copy, modify, distribute and sell this software
  6.  * and its documentation for any purpose is hereby granted without fee,
  7.  * provided that the above copyright notice appear in all copies and
  8.  * that both that copyright notice and this permission notice appear
  9.  * in supporting documentation.  Silicon Graphics makes no
  10.  * representations about the suitability of this software for any
  11.  * purpose.  It is provided "as is" without express or implied warranty.
  12.  *
  13.  */
  14.  
  15. /* NOTE: This is an internal header file, included by other STL headers.
  16.  *   You should not attempt to use it directly.
  17.  */
  18.  
  19. #ifndef __SGI_STL_INTERNAL_SLIST_H
  20. #define __SGI_STL_INTERNAL_SLIST_H
  21.  
  22.  
  23. __STL_BEGIN_NAMESPACE 
  24.  
  25. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  26. #pragma set woff 1174
  27. #endif
  28.  
  29. struct __slist_node_base
  30. {
  31.   __slist_node_base* next;
  32. };
  33.  
  34. inline __slist_node_base* __slist_make_link(__slist_node_base* prev_node,
  35.                                             __slist_node_base* new_node)
  36. {
  37.   new_node->next = prev_node->next;
  38.   prev_node->next = new_node;
  39.   return new_node;
  40. }
  41.  
  42. inline __slist_node_base* __slist_previous(__slist_node_base* head,
  43.                                            const __slist_node_base* node)
  44. {
  45.   while (head && head->next != node)
  46.     head = head->next;
  47.   return head;
  48. }
  49.  
  50. inline const __slist_node_base* __slist_previous(const __slist_node_base* head,
  51.                                                  const __slist_node_base* node)
  52. {
  53.   while (head && head->next != node)
  54.     head = head->next;
  55.   return head;
  56. }
  57.  
  58. inline void __slist_splice_after(__slist_node_base* pos,
  59.                                  __slist_node_base* before_first,
  60.                                  __slist_node_base* before_last)
  61. {
  62.   if (pos != before_first && pos != before_last) {
  63.     __slist_node_base* first = before_first->next;
  64.     __slist_node_base* after = pos->next;
  65.     before_first->next = before_last->next;
  66.     pos->next = first;
  67.     before_last->next = after;
  68.   }
  69. }
  70.  
  71. inline __slist_node_base* __slist_reverse(__slist_node_base* node)
  72. {
  73.   __slist_node_base* result = node;
  74.   node = node->next;
  75.   result->next = 0;
  76.   while(node) {
  77.     __slist_node_base* next = node->next;
  78.     node->next = result;
  79.     result = node;
  80.     node = next;
  81.   }
  82.   return result;
  83. }
  84.  
  85. template <class T>
  86. struct __slist_node : public __slist_node_base
  87. {
  88.   T data;
  89. };
  90.  
  91. struct __slist_iterator_base
  92. {
  93.   typedef size_t size_type;
  94.   typedef ptrdiff_t difference_type;
  95.   typedef forward_iterator_tag iterator_category;
  96.  
  97.   __slist_node_base* node;
  98.  
  99.   __slist_iterator_base(__slist_node_base* x) : node(x) {}
  100.   void incr() { node = node->next; }
  101.  
  102.   bool operator==(const __slist_iterator_base& x) const {
  103.     return node == x.node;
  104.   }
  105.   bool operator!=(const __slist_iterator_base& x) const {
  106.     return node != x.node;
  107.   }
  108. };
  109.  
  110. template <class T, class Ref, class Ptr>
  111. struct __slist_iterator : public __slist_iterator_base
  112. {
  113.   typedef __slist_iterator<T, T&, T*>             iterator;
  114.   typedef __slist_iterator<T, const T&, const T*> const_iterator;
  115.   typedef __slist_iterator<T, Ref, Ptr>           self;
  116.  
  117.   typedef T value_type;
  118.   typedef Ptr pointer;
  119.   typedef Ref reference;
  120.   typedef __slist_node<T> list_node;
  121.  
  122.   __slist_iterator(list_node* x) : __slist_iterator_base(x) {}
  123.   __slist_iterator() : __slist_iterator_base(0) {}
  124.   __slist_iterator(const iterator& x) : __slist_iterator_base(x.node) {}
  125.  
  126.   reference operator*() const { return ((list_node*) node)->data; }
  127. #ifndef __SGI_STL_NO_ARROW_OPERATOR
  128.   pointer operator->() const { return &(operator*()); }
  129. #endif /* __SGI_STL_NO_ARROW_OPERATOR */
  130.  
  131.   self& operator++()
  132.   {
  133.     incr();
  134.     return *this;
  135.   }
  136.   self operator++(int)
  137.   {
  138.     self tmp = *this;
  139.     incr();
  140.     return tmp;
  141.   }
  142. };
  143.  
  144. #ifndef __STL_CLASS_PARTIAL_SPECIALIZATION
  145.  
  146. inline ptrdiff_t*
  147. distance_type(const __slist_iterator_base&)
  148. {
  149.   return 0;
  150. }
  151.  
  152. inline forward_iterator_tag
  153. iterator_category(const __slist_iterator_base&)
  154. {
  155.   return forward_iterator_tag();
  156. }
  157.  
  158. template <class T, class Ref, class Ptr> 
  159. inline T* 
  160. value_type(const __slist_iterator<T, Ref, Ptr>&) {
  161.   return 0;
  162. }
  163.  
  164. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  165.  
  166. inline size_t __slist_size(__slist_node_base* node)
  167. {
  168.   size_t result = 0;
  169.   for ( ; node != 0; node = node->next)
  170.     ++result;
  171.   return result;
  172. }
  173.  
  174. template <class T, class Alloc = alloc>
  175. class slist
  176. {
  177. public:
  178.   typedef T value_type;
  179.   typedef value_type* pointer;
  180.   typedef const value_type* const_pointer;
  181.   typedef value_type& reference;
  182.   typedef const value_type& const_reference;
  183.   typedef size_t size_type;
  184.   typedef ptrdiff_t difference_type;
  185.  
  186.   typedef __slist_iterator<T, T&, T*>             iterator;
  187.   typedef __slist_iterator<T, const T&, const T*> const_iterator;
  188.  
  189. private:
  190.   typedef __slist_node<T> list_node;
  191.   typedef __slist_node_base list_node_base;
  192.   typedef __slist_iterator_base iterator_base;
  193.   typedef simple_alloc<list_node, Alloc> list_node_allocator;
  194.  
  195.   static list_node* create_node(const value_type& x) {
  196.     list_node* node = list_node_allocator::allocate();
  197.     __STL_TRY {
  198.       construct(&node->data, x);
  199.       node->next = 0;
  200.     }
  201.     __STL_UNWIND(list_node_allocator::deallocate(node));
  202.     return node;
  203.   }
  204.   
  205.   static void destroy_node(list_node* node) {
  206.     destroy(&node->data);
  207.     list_node_allocator::deallocate(node);
  208.   }
  209.  
  210.   void fill_initialize(size_type n, const value_type& x) {
  211.     head.next = 0;
  212.     __STL_TRY {
  213.       _insert_after_fill(&head, n, x);
  214.     }
  215.     __STL_UNWIND(clear());
  216.   }    
  217.  
  218. #ifdef __STL_MEMBER_TEMPLATES
  219.   template <class InputIterator>
  220.   void range_initialize(InputIterator first, InputIterator last) {
  221.     head.next = 0;
  222.     __STL_TRY {
  223.       _insert_after_range(&head, first, last);
  224.     }
  225.     __STL_UNWIND(clear());
  226.   }
  227. #else /* __STL_MEMBER_TEMPLATES */
  228.   void range_initialize(const value_type* first, const value_type* last) {
  229.     head.next = 0;
  230.     __STL_TRY {
  231.       _insert_after_range(&head, first, last);
  232.     }
  233.     __STL_UNWIND(clear());
  234.   }
  235.   void range_initialize(const_iterator first, const_iterator last) {
  236.     head.next = 0;
  237.     __STL_TRY {
  238.       _insert_after_range(&head, first, last);
  239.     }
  240.     __STL_UNWIND(clear());
  241.   }
  242. #endif /* __STL_MEMBER_TEMPLATES */
  243.  
  244. private:
  245.   list_node_base head;
  246.  
  247. public:
  248.   slist() { head.next = 0; }
  249.  
  250.   slist(size_type n, const value_type& x) { fill_initialize(n, x); }
  251.   slist(int n, const value_type& x) { fill_initialize(n, x); }
  252.   slist(long n, const value_type& x) { fill_initialize(n, x); }
  253.   explicit slist(size_type n) { fill_initialize(n, value_type()); }
  254.  
  255. #ifdef __STL_MEMBER_TEMPLATES
  256.   template <class InputIterator>
  257.   slist(InputIterator first, InputIterator last) {
  258.     range_initialize(first, last);
  259.   }
  260.  
  261. #else /* __STL_MEMBER_TEMPLATES */
  262.   slist(const_iterator first, const_iterator last) {
  263.     range_initialize(first, last);
  264.   }
  265.   slist(const value_type* first, const value_type* last) {
  266.     range_initialize(first, last);
  267.   }
  268. #endif /* __STL_MEMBER_TEMPLATES */
  269.  
  270.   slist(const slist& L) { range_initialize(L.begin(), L.end()); }
  271.  
  272.   slist& operator= (const slist& L);
  273.  
  274.   ~slist() { clear(); }
  275.  
  276. public:
  277.  
  278.   iterator begin() { return iterator((list_node*)head.next); }
  279.   const_iterator begin() const { return const_iterator((list_node*)head.next);}
  280.  
  281.   iterator end() { return iterator(0); }
  282.   const_iterator end() const { return const_iterator(0); }
  283.  
  284.   size_type size() const { return __slist_size(head.next); }
  285.   
  286.   size_type max_size() const { return size_type(-1); }
  287.  
  288.   bool empty() const { return head.next == 0; }
  289.  
  290.   void swap(slist& L)
  291.   {
  292.     list_node_base* tmp = head.next;
  293.     head.next = L.head.next;
  294.     L.head.next = tmp;
  295.   }
  296.  
  297. public:
  298.   friend bool operator== __STL_NULL_TMPL_ARGS(const slist<T, Alloc>& L1,
  299.                                               const slist<T, Alloc>& L2);
  300.  
  301. public:
  302.  
  303.   reference front() { return ((list_node*) head.next)->data; }
  304.   const_reference front() const { return ((list_node*) head.next)->data; }
  305.   void push_front(const value_type& x)   {
  306.     __slist_make_link(&head, create_node(x));
  307.   }
  308.   void pop_front() {
  309.     list_node* node = (list_node*) head.next;
  310.     head.next = node->next;
  311.     destroy_node(node);
  312.   }
  313.  
  314.   iterator previous(const_iterator pos) {
  315.     return iterator((list_node*) __slist_previous(&head, pos.node));
  316.   }
  317.   const_iterator previous(const_iterator pos) const {
  318.     return const_iterator((list_node*) __slist_previous(&head, pos.node));
  319.   }
  320.  
  321. private:
  322.   list_node* _insert_after(list_node_base* pos, const value_type& x) {
  323.     return (list_node*) (__slist_make_link(pos, create_node(x)));
  324.   }
  325.  
  326.   void _insert_after_fill(list_node_base* pos,
  327.                           size_type n, const value_type& x) {
  328.     for (size_type i = 0; i < n; ++i)
  329.       pos = __slist_make_link(pos, create_node(x));
  330.   }
  331.  
  332. #ifdef __STL_MEMBER_TEMPLATES
  333.   template <class InIter>
  334.   void _insert_after_range(list_node_base* pos, InIter first, InIter last) {
  335.     while (first != last) {
  336.       pos = __slist_make_link(pos, create_node(*first));
  337.       ++first;
  338.     }
  339.   }
  340. #else /* __STL_MEMBER_TEMPLATES */
  341.   void _insert_after_range(list_node_base* pos,
  342.                            const_iterator first, const_iterator last) {
  343.     while (first != last) {
  344.       pos = __slist_make_link(pos, create_node(*first));
  345.       ++first;
  346.     }
  347.   }
  348.   void _insert_after_range(list_node_base* pos,
  349.                            const value_type* first, const value_type* last) {
  350.     while (first != last) {
  351.       pos = __slist_make_link(pos, create_node(*first));
  352.       ++first;
  353.     }
  354.   }
  355. #endif /* __STL_MEMBER_TEMPLATES */
  356.  
  357.   list_node_base* erase_after(list_node_base* pos) {
  358.     list_node* next = (list_node*) (pos->next);
  359.     list_node_base* next_next = next->next;
  360.     pos->next = next_next;
  361.     destroy_node(next);
  362.     return next_next;
  363.   }
  364.    
  365.   list_node_base* erase_after(list_node_base* before_first,
  366.                               list_node_base* last_node) {
  367.     list_node* cur = (list_node*) (before_first->next);
  368.     while (cur != last_node) {
  369.       list_node* tmp = cur;
  370.       cur = (list_node*) cur->next;
  371.       destroy_node(tmp);
  372.     }
  373.     before_first->next = last_node;
  374.     return last_node;
  375.   }
  376.  
  377.  
  378. public:
  379.  
  380.   iterator insert_after(iterator pos, const value_type& x) {
  381.     return iterator(_insert_after(pos.node, x));
  382.   }
  383.  
  384.   iterator insert_after(iterator pos) {
  385.     return insert_after(pos, value_type());
  386.   }
  387.  
  388.   void insert_after(iterator pos, size_type n, const value_type& x) {
  389.     _insert_after_fill(pos.node, n, x);
  390.   }
  391.   void insert_after(iterator pos, int n, const value_type& x) {
  392.     _insert_after_fill(pos.node, (size_type) n, x);
  393.   }
  394.   void insert_after(iterator pos, long n, const value_type& x) {
  395.     _insert_after_fill(pos.node, (size_type) n, x);
  396.   }
  397.  
  398. #ifdef __STL_MEMBER_TEMPLATES
  399.   template <class InIter>
  400.   void insert_after(iterator pos, InIter first, InIter last) {
  401.     _insert_after_range(pos.node, first, last);
  402.   }
  403. #else /* __STL_MEMBER_TEMPLATES */
  404.   void insert_after(iterator pos, const_iterator first, const_iterator last) {
  405.     _insert_after_range(pos.node, first, last);
  406.   }
  407.   void insert_after(iterator pos,
  408.                     const value_type* first, const value_type* last) {
  409.     _insert_after_range(pos.node, first, last);
  410.   }
  411. #endif /* __STL_MEMBER_TEMPLATES */
  412.  
  413.   iterator insert(iterator pos, const value_type& x) {
  414.     return iterator(_insert_after(__slist_previous(&head, pos.node), x));
  415.   }
  416.  
  417.   iterator insert(iterator pos) {
  418.     return iterator(_insert_after(__slist_previous(&head, pos.node),
  419.                                   value_type()));
  420.   }
  421.  
  422.   void insert(iterator pos, size_type n, const value_type& x) {
  423.     _insert_after_fill(__slist_previous(&head, pos.node), n, x);
  424.   } 
  425.   void insert(iterator pos, int n, const value_type& x) {
  426.     _insert_after_fill(__slist_previous(&head, pos.node), (size_type) n, x);
  427.   } 
  428.   void insert(iterator pos, long n, const value_type& x) {
  429.     _insert_after_fill(__slist_previous(&head, pos.node), (size_type) n, x);
  430.   } 
  431.     
  432. #ifdef __STL_MEMBER_TEMPLATES
  433.   template <class InIter>
  434.   void insert(iterator pos, InIter first, InIter last) {
  435.     _insert_after_range(__slist_previous(&head, pos.node), first, last);
  436.   }
  437. #else /* __STL_MEMBER_TEMPLATES */
  438.   void insert(iterator pos, const_iterator first, const_iterator last) {
  439.     _insert_after_range(__slist_previous(&head, pos.node), first, last);
  440.   }
  441.   void insert(iterator pos, const value_type* first, const value_type* last) {
  442.     _insert_after_range(__slist_previous(&head, pos.node), first, last);
  443.   }
  444. #endif /* __STL_MEMBER_TEMPLATES */
  445.  
  446.  
  447. public:
  448.   iterator erase_after(iterator pos) {
  449.     return iterator((list_node*)erase_after(pos.node));
  450.   }
  451.   iterator erase_after(iterator before_first, iterator last) {
  452.     return iterator((list_node*)erase_after(before_first.node, last.node));
  453.   }
  454.  
  455.   iterator erase(iterator pos) {
  456.     return (list_node*) erase_after(__slist_previous(&head, pos.node));
  457.   }
  458.   iterator erase(iterator first, iterator last) {
  459.     return (list_node*) erase_after(__slist_previous(&head, first.node),
  460.                                     last.node);
  461.   }
  462.  
  463.   void resize(size_type new_size, const T& x);
  464.   void resize(size_type new_size) { resize(new_size, T()); }
  465.   void clear() { erase_after(&head, 0); }
  466.  
  467. public:
  468.   // Moves the range [before_first + 1, before_last + 1) to *this,
  469.   //  inserting it immediately after pos.  This is constant time.
  470.   void splice_after(iterator pos, 
  471.                     iterator before_first, iterator before_last)
  472.   {
  473.     if (before_first != before_last) 
  474.       __slist_splice_after(pos.node, before_first.node, before_last.node);
  475.   }
  476.  
  477.   // Moves the element that follows prev to *this, inserting it immediately
  478.   //  after pos.  This is constant time.
  479.   void splice_after(iterator pos, iterator prev)
  480.   {
  481.     __slist_splice_after(pos.node, prev.node, prev.node->next);
  482.   }
  483.  
  484.  
  485.   // Linear in distance(begin(), pos), and linear in L.size().
  486.   void splice(iterator pos, slist& L) {
  487.     if (L.head.next)
  488.       __slist_splice_after(__slist_previous(&head, pos.node),
  489.                            &L.head,
  490.                            __slist_previous(&L.head, 0));
  491.   }
  492.  
  493.   // Linear in distance(begin(), pos), and in distance(L.begin(), i).
  494.   void splice(iterator pos, slist& L, iterator i) {
  495.     __slist_splice_after(__slist_previous(&head, pos.node),
  496.                          __slist_previous(&L.head, i.node),
  497.                          i.node);
  498.   }
  499.  
  500.   // Linear in distance(begin(), pos), in distance(L.begin(), first),
  501.   // and in distance(first, last).
  502.   void splice(iterator pos, slist& L, iterator first, iterator last)
  503.   {
  504.     if (first != last)
  505.       __slist_splice_after(__slist_previous(&head, pos.node),
  506.                            __slist_previous(&L.head, first.node),
  507.                            __slist_previous(first.node, last.node));
  508.   }
  509.  
  510. public:
  511.   void reverse() { if (head.next) head.next = __slist_reverse(head.next); }
  512.  
  513.   void remove(const T& val); 
  514.   void unique(); 
  515.   void merge(slist& L);
  516.   void sort();     
  517.  
  518. #ifdef __STL_MEMBER_TEMPLATES
  519.   template <class Predicate> void remove_if(Predicate pred);
  520.   template <class BinaryPredicate> void unique(BinaryPredicate pred); 
  521.   template <class StrictWeakOrdering> void merge(slist&, StrictWeakOrdering); 
  522.   template <class StrictWeakOrdering> void sort(StrictWeakOrdering comp); 
  523. #endif /* __STL_MEMBER_TEMPLATES */
  524. };
  525.  
  526. template <class T, class Alloc>
  527. slist<T, Alloc>& slist<T,Alloc>::operator=(const slist<T, Alloc>& L)
  528. {
  529.   if (&L != this) {
  530.     list_node_base* p1 = &head;
  531.     list_node* n1 = (list_node*) head.next;
  532.     const list_node* n2 = (const list_node*) L.head.next;
  533.     while (n1 && n2) {
  534.       n1->data = n2->data;
  535.       p1 = n1;
  536.       n1 = (list_node*) n1->next;
  537.       n2 = (const list_node*) n2->next;
  538.     }
  539.     if (n2 == 0)
  540.       erase_after(p1, 0);
  541.     else
  542.       _insert_after_range(p1,
  543.                           const_iterator((list_node*)n2), const_iterator(0));
  544.   }
  545.   return *this;
  546. } 
  547.  
  548. template <class T, class Alloc>
  549. bool operator==(const slist<T, Alloc>& L1, const slist<T, Alloc>& L2)
  550. {
  551.   typedef typename slist<T,Alloc>::list_node list_node;
  552.   list_node* n1 = (list_node*) L1.head.next;
  553.   list_node* n2 = (list_node*) L2.head.next;
  554.   while (n1 && n2 && n1->data == n2->data) {
  555.     n1 = (list_node*) n1->next;
  556.     n2 = (list_node*) n2->next;
  557.   }
  558.   return n1 == 0 && n2 == 0;
  559. }
  560.  
  561. template <class T, class Alloc>
  562. inline bool operator<(const slist<T, Alloc>& L1, const slist<T, Alloc>& L2)
  563. {
  564.   return lexicographical_compare(L1.begin(), L1.end(), L2.begin(), L2.end());
  565. }
  566.  
  567. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  568.  
  569. template <class T, class Alloc>
  570. inline void swap(slist<T, Alloc>& x, slist<T, Alloc>& y) {
  571.   x.swap(y);
  572. }
  573.  
  574. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  575.  
  576.  
  577. template <class T, class Alloc>
  578. void slist<T, Alloc>::resize(size_type len, const T& x)
  579. {
  580.   list_node_base* cur = &head;
  581.   while (cur->next != 0 && len > 0) {
  582.     --len;
  583.     cur = cur->next;
  584.   }
  585.   if (cur->next) 
  586.     erase_after(cur, 0);
  587.   else
  588.     _insert_after_fill(cur, len, x);
  589. }
  590.  
  591. template <class T, class Alloc>
  592. void slist<T,Alloc>::remove(const T& val)
  593. {
  594.   list_node_base* cur = &head;
  595.   while (cur && cur->next) {
  596.     if (((list_node*) cur->next)->data == val)
  597.       erase_after(cur);
  598.     else
  599.       cur = cur->next;
  600.   }
  601. }
  602.  
  603. template <class T, class Alloc> 
  604. void slist<T,Alloc>::unique()
  605. {
  606.   list_node_base* cur = head.next;
  607.   if (cur) {
  608.     while (cur->next) {
  609.       if (((list_node*)cur)->data == ((list_node*)(cur->next))->data)
  610.         erase_after(cur);
  611.       else
  612.         cur = cur->next;
  613.     }
  614.   }
  615. }
  616.  
  617. template <class T, class Alloc>
  618. void slist<T,Alloc>::merge(slist<T,Alloc>& L)
  619. {
  620.   list_node_base* n1 = &head;
  621.   while (n1->next && L.head.next) {
  622.     if (((list_node*) L.head.next)->data < ((list_node*) n1->next)->data) 
  623.       __slist_splice_after(n1, &L.head, L.head.next);
  624.     n1 = n1->next;
  625.   }
  626.   if (L.head.next) {
  627.     n1->next = L.head.next;
  628.     L.head.next = 0;
  629.   }
  630. }
  631.  
  632. template <class T, class Alloc>
  633. void slist<T,Alloc>::sort()
  634. {
  635.   if (head.next && head.next->next) {
  636.     slist carry;
  637.     slist counter[64];
  638.     int fill = 0;
  639.     while (!empty()) {
  640.       __slist_splice_after(&carry.head, &head, head.next);
  641.       int i = 0;
  642.       while (i < fill && !counter[i].empty()) {
  643.         counter[i].merge(carry);
  644.         carry.swap(counter[i]);
  645.         ++i;
  646.       }
  647.       carry.swap(counter[i]);
  648.       if (i == fill)
  649.         ++fill;
  650.     }
  651.  
  652.     for (int i = 1; i < fill; ++i)
  653.       counter[i].merge(counter[i-1]);
  654.     this->swap(counter[fill-1]);
  655.   }
  656. }
  657.  
  658. #ifdef __STL_MEMBER_TEMPLATES
  659.  
  660. template <class T, class Alloc> 
  661. template <class Predicate> void slist<T,Alloc>::remove_if(Predicate pred)
  662. {
  663.   list_node_base* cur = &head;
  664.   while (cur->next) {
  665.     if (pred(((list_node*) cur->next)->data))
  666.       erase_after(cur);
  667.     else
  668.       cur = cur->next;
  669.   }
  670. }
  671.  
  672. template <class T, class Alloc> template <class BinaryPredicate> 
  673. void slist<T,Alloc>::unique(BinaryPredicate pred)
  674. {
  675.   list_node* cur = (list_node*) head.next;
  676.   if (cur) {
  677.     while (cur->next) {
  678.       if (pred(((list_node*)cur)->data, ((list_node*)(cur->next))->data))
  679.         erase_after(cur);
  680.       else
  681.         cur = (list_node*) cur->next;
  682.     }
  683.   }
  684. }
  685.  
  686. template <class T, class Alloc> template <class StrictWeakOrdering>
  687. void slist<T,Alloc>::merge(slist<T,Alloc>& L, StrictWeakOrdering comp)
  688. {
  689.   list_node_base* n1 = &head;
  690.   while (n1->next && L.head.next) {
  691.     if (comp(((list_node*) L.head.next)->data,
  692.              ((list_node*) n1->next)->data))
  693.       __slist_splice_after(n1, &L.head, L.head.next);
  694.     n1 = n1->next;
  695.   }
  696.   if (L.head.next) {
  697.     n1->next = L.head.next;
  698.     L.head.next = 0;
  699.   }
  700. }
  701.  
  702. template <class T, class Alloc> template <class StrictWeakOrdering> 
  703. void slist<T,Alloc>::sort(StrictWeakOrdering comp)
  704. {
  705.   if (head.next && head.next->next) {
  706.     slist carry;
  707.     slist counter[64];
  708.     int fill = 0;
  709.     while (!empty()) {
  710.       __slist_splice_after(&carry.head, &head, head.next);
  711.       int i = 0;
  712.       while (i < fill && !counter[i].empty()) {
  713.         counter[i].merge(carry, comp);
  714.         carry.swap(counter[i]);
  715.         ++i;
  716.       }
  717.       carry.swap(counter[i]);
  718.       if (i == fill)
  719.         ++fill;
  720.     }
  721.  
  722.     for (int i = 1; i < fill; ++i)
  723.       counter[i].merge(counter[i-1], comp);
  724.     this->swap(counter[fill-1]);
  725.   }
  726. }
  727.  
  728. #endif /* __STL_MEMBER_TEMPLATES */
  729.  
  730. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  731. #pragma reset woff 1174
  732. #endif
  733.  
  734. __STL_END_NAMESPACE 
  735.  
  736. #endif /* __SGI_STL_INTERNAL_SLIST_H */
  737.  
  738. // Local Variables:
  739. // mode:C++
  740. // End:
  741.